package LeetCode;

import java.util.Arrays;

public class LC_164_MaximumGap {

    public static void main(String[] args) {

    }

    static class Solution {
        public int maximumGap(int[] nums) {
            if (nums == null || nums.length < 2) return 0;

            int len = nums.length;
            int max = nums[0], min = nums[0];
            for (int i = 0; i < nums.length; i++) {
                max = Math.max(max, nums[i]);
                min = Math.min(min, nums[i]);
            }
            //Math.ceil与最小的比这个数大的蒸熟，使bucket可以包含所有数
            int gap = (int) Math.ceil((double) (max - min) / (len - 1));

            int[] BucketsMIN = new int[len - 1];
            int[] BucketsMAX = new int[len - 1];
            Arrays.fill(BucketsMIN, Integer.MAX_VALUE);
            Arrays.fill(BucketsMAX, Integer.MIN_VALUE);
            for (int num : nums) {
                //不考虑边界，所以把边界的min和max都拿出来，单独再考虑
                if (num == min || num == max) continue;
                int bucket = (num - min) / gap;
                BucketsMIN[bucket] = Math.min(BucketsMIN[bucket], num);
                BucketsMAX[bucket] = Math.max(BucketsMAX[bucket], num);
            }

            int result = 0;
            int previous = min;
            for (int i = 0; i < len - 1; i++) {
                if (BucketsMIN[i] == Integer.MAX_VALUE && BucketsMAX[i] == Integer.MIN_VALUE) continue;
                result = Math.max(result, BucketsMIN[i] - previous);
                previous = BucketsMAX[i];
            }
            result = Math.max(result, max - previous);
            return result;
        }
    }

}